﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0157_GenerateMatrix : IAlgorithm
    {
        // 59. 螺旋矩阵 II

        // 给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

        // 提示：
        //  1 <= n <= 20

        public void Test()
        {
            var res = GenerateMatrix(2);
            foreach (var item in res)
            {
                foreach (var iitem in item)
                {
                    Console.Write(iitem + " ");
                }
                Console.WriteLine();
            }
        }

        // 算法
        public int[][] GenerateMatrix(int n)
        {
            var res = new int[n][];
            for (int i = 0; i < n; i++)
                res[i] = new int[n];
            int row = 0, column = 0;
            int[][] directions = { new int[]{ 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } }; // 右下左上
            int directionIndex = 0;
            int curNum = 1;
            while (curNum <= n*n)
            {
                res[row][column] = curNum;
                curNum++;
                int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
                if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || res[nextRow][nextColumn] != 0)
                {
                    directionIndex = (directionIndex + 1) % 4; 
                }
                row += directions[directionIndex][0];
                column += directions[directionIndex][1];
            }
            return res;
        }
    }
}
